<html>
<head><meta charset="utf-8"><title>Comparison of rust-analyzer&#x27;s parser with tree-sitter? · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html">Comparison of rust-analyzer&#x27;s parser with tree-sitter?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="205086108"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205086108" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205086108">(Jul 27 2020 at 06:53)</a>:</h4>
<p>I'm curious how does rust-analyzer's parser compare with tree-sitter in terms of error recovery and incremental parsing? For example, what would be better or worse if I replaced rust-analyzer's parser with <a href="https://github.com/tree-sitter/tree-sitter-rust">tree-sitter-rust</a>?</p>



<a name="205088673"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205088673" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205088673">(Jul 27 2020 at 07:38)</a>:</h4>
<p>In terms of error recovery, rust-analyzer's parser is better (though this might be an artifact of how a specific grammar is specified in tree-sitter, I haven't looked very closely into this). In terms of incrementality, tree-sitter is better. </p>
<p>Replacing our parser with tree sitter would be much worse, but not because of these two metrics.</p>



<a name="205088721"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205088721" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205088721">(Jul 27 2020 at 07:39)</a>:</h4>
<p>The amount of accidental complexity to pull in a parser generator is big. It is generally justified when you need to parse a lot of languages. But we only need to parse one, so, in terms of overall cost, I expect a hand-written parser to be much more efficient.</p>



<a name="205089575"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205089575" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205089575">(Jul 27 2020 at 07:53)</a>:</h4>
<p>Thanks! Why is error recovery better in rust-analyzer? Is it because we can do language-specific decisions on how to recover (which tree-sitter cannot do as far as I understand from the <a href="https://tree-sitter.github.io/tree-sitter/creating-parsers">documentation</a>)? Is there a summary on how error recovery in parsing is done in rust-analyzer currently? Or else where do I look in the source code?</p>



<a name="205089793"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205089793" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205089793">(Jul 27 2020 at 07:57)</a>:</h4>
<p><a href="https://matklad.github.io/2018/06/06/modern-parser-generator.html#abandoning-cfg">https://matklad.github.io/2018/06/06/modern-parser-generator.html#abandoning-cfg</a> (from "The most important feature of hand-written parsers is a great support for error recovery and partial parses. It")</p>



<a name="205089804"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205089804" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205089804">(Jul 27 2020 at 07:57)</a>:</h4>
<p>For the example, rust-analyze gives</p>
<div class="codehilite"><pre><span></span><code>SOURCE_FILE@0..22597
  FN_DEF@0..7
    FN_KW@0..2 &quot;fn&quot;
    WHITESPACE@2..3 &quot; &quot;
    NAME@3..6
      IDENT@3..6 &quot;foo&quot;
    PARAM_LIST@6..7
      L_PAREN@6..7 &quot;(&quot;
  WHITESPACE@7..9 &quot;\n\n&quot;
  STRUCT_DEF@9..31
    STRUCT_KW@9..15 &quot;struct&quot;
    WHITESPACE@15..16 &quot; &quot;
    NAME@16..17
      IDENT@16..17 &quot;S&quot;
    WHITESPACE@17..18 &quot; &quot;
    RECORD_FIELD_DEF_LIST@18..31
      L_CURLY@18..19 &quot;{&quot;
      WHITESPACE@19..23 &quot;\n   &quot;
      RECORD_FIELD_DEF@23..29
        NAME@23..24
          IDENT@23..24 &quot;f&quot;
        COLON@24..25 &quot;:&quot;
        WHITESPACE@25..26 &quot; &quot;
        PATH_TYPE@26..29
          PATH@26..29
            PATH_SEGMENT@26..29
              NAME_REF@26..29
                IDENT@26..29 &quot;u32&quot;
      WHITESPACE@29..30 &quot;\n&quot;
      R_CURLY@30..31 &quot;}&quot;
</code></pre></div>



<a name="205089825"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205089825" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205089825">(Jul 27 2020 at 07:57)</a>:</h4>
<p>tree sitter</p>
<div class="codehilite"><pre><span></span><code>source_file [0, 0] - [5, 0])
  ERROR [0, 0] - [4, 1])
    identifier [0, 3] - [0, 6])
    struct_pattern [2, 0] - [4, 1])
      type: type_identifier [2, 0] - [2, 6])
      ERROR [2, 7] - [2, 8])
        identifier [2, 7] - [2, 8])
      field_pattern [3, 3] - [3, 9])
        name: field_identifier [3, 3] - [3, 4])
        pattern: identifier [3, 6] - [3, 9])
</code></pre></div>



<a name="205089885"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205089885" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205089885">(Jul 27 2020 at 07:58)</a>:</h4>
<p>Interesting! Thanks for the concrete example and the blog post, I'll read it. What's  the source that you're parsing in these examples?</p>



<a name="205089894"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205089894" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205089894">(Jul 27 2020 at 07:58)</a>:</h4>
<p>The example in the post</p>



<a name="205102461"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205102461" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> osa1 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205102461">(Jul 27 2020 at 10:46)</a>:</h4>
<p>Hey <span class="user-mention" data-user-id="133169">@matklad</span> -- thanks for the answers, they're really helpful. I want to look at rust-analyzer source for the error recovery code used in the example above, where should I look?</p>



<a name="205103495"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205103495" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205103495">(Jul 27 2020 at 11:00)</a>:</h4>
<p><a href="https://github.com/rust-analyzer/rust-analyzer/blob/bc9fab156596d05ddb6b3fa57acd0fbd0755f2a0/crates/ra_parser/src/grammar/items.rs#L322-L352">https://github.com/rust-analyzer/rust-analyzer/blob/bc9fab156596d05ddb6b3fa57acd0fbd0755f2a0/crates/ra_parser/src/grammar/items.rs#L322-L352</a></p>



<a name="205103770"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205103770" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205103770">(Jul 27 2020 at 11:04)</a>:</h4>
<p>Unrelated, but there's this pattern here: <a href="https://github.com/rust-analyzer/rust-analyzer/blob/bc9fab156596d05ddb6b3fa57acd0fbd0755f2a0/crates/ra_parser/src/grammar/items.rs#L347-L351">https://github.com/rust-analyzer/rust-analyzer/blob/bc9fab156596d05ddb6b3fa57acd0fbd0755f2a0/crates/ra_parser/src/grammar/items.rs#L347-L351</a></p>



<a name="205103787"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Comparison%20of%20rust-analyzer%27s%20parser%20with%20tree-sitter%3F/near/205103787" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Comparison.20of.20rust-analyzer&#x27;s.20parser.20with.20tree-sitter.3F.html#205103787">(Jul 27 2020 at 11:04)</a>:</h4>
<p><code>eat</code> already checks the current token and returns <code>false</code> if they don't match. EDIT: ah, it's <code>bump</code>, not <code>eat</code>, and I guess it's not so common, so it's probably fine.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>